//
//  main.c
//  Questions
//
//  Created by wangrui.
//  Copyright (c) 2014年 wangrui. All rights reserved.
//

/*
 *图(无向)的最小生成树 prim算法堆优化
 *
 *2014-10-09 15:20:58
 *测试数据:
	6 9
	2 4 11
	3 5 13
	4 6 3
	5 6 4
	2 3 6
	4 5 7
	1 2 1
	3 4 9
	1 3 2
 */

#include <stdio.h>
#include <stdlib.h>
#include "cutils.h"

#ifdef DEBUG
#undef DEBUG
#define DEBUG 0
#endif

#define INF 999999
#define MaxSize 100
int pos[MaxSize];
int dis[MaxSize];

void swapAndChangePos(int *a, int  *b)
{
	int t = *a;
	*a = *b;
	*b = t;
	
	t = pos[*a];
	pos[*a] = pos[*b];
	pos[*b] = t;
}

void siftdown(int tree[], int idx,int n) {
	int t,flag = 0;
	
	while (idx*2 <= n && flag == 0) {
		
		if (dis[tree[idx]] > dis[tree[2*idx]]) {//特别注意:这里是依靠dis数组对应的值大小，来决定是不是要交换堆
			t = 2 * idx;
		}
		else {
			t = idx;
		}
		
		if (2*idx + 1 <= n) { //有右节点
			if (dis[tree[t]] > dis[tree[2*idx+1]]) { //特别注意:这里是依靠dis数组对应的值大小，来决定是不是要交换堆
				t = 2*idx + 1;
			}
		}
		
		if (t != idx) {
			swapAndChangePos(&tree[idx], &tree[t]);
			idx = t;
		}
		else{
			flag = 1;
		}
	}
	
}

void siftup(int tree[],int idx) {
	int flag = 0;
	while (idx != 1 && flag == 0) {//非堆顶
		if(dis[tree[idx]] < dis[tree[idx/2]]){
			swapAndChangePos(&tree[idx], &tree[idx/2]);
		}
		else{
			flag = 1 ;
		}
		
		idx /= 2;
	}
}

int deleteTop(int tree[],int *num) {
	
	int temp = tree[1];
	pos[temp] = 0;
	
	tree[1] = tree[*num];
	pos[tree[1]] = 1;
	
	*num = *num - 1; //这行代码非常重要
	siftdown(tree, 1, *num); //调整堆顶
	
	return temp;
}

void heapAdjust(int tree[], int n) {
	for (int i = n/2; i>=1; i--) {
		siftdown(tree, i, n);
	}
}

int main(int argc, const char * argv[])
{
	
	int n,m;
	scanf("%d %d",&n,&m);
	
	int u[2*m+1], v[2*m+1], w[2*m+1];//因为是无向图，多一倍m空间
	int first[n+1],next[2*m+1];
	
	for(int i=1; i<=m; i++) {
		scanf("%d %d %d", &u[i],&v[i],&w[i]);
	}
	
	//反向存储剩下的边
	for (int i=m+1; i<=2*m; i++) {
		u[i] = v[i-m]; //注意这里要交换
		v[i] = u[i-m];
		w[i] = w[i-m];
	}

#if DEBUG
	printArray(u+1, 2*m);
	printArray(v+1, 2*m);
	printArray(w+1, 2*m);
#endif
	
	//使用邻接表存储
	for(int i=0; i<=n; i++) {
		first[i] = -1;
	}
	
	for (int i=1; i<=2*m; i++) {
		next[i]	= first[u[i]];
		first[u[i]] = i;
	}

#if DEBUG
	printArray(first+1, n);
	printArray(next+1, 2*m);
#endif

	int flag[n+1],count=0, sum=0;
	
	//初始化数组
	for (int i=0; i<=n; i++) {
		dis[i] = INF;
		flag[i] = 0;
	}
	dis[1] = 0;
	
	int k = first[1];
	while (k != -1) {
		dis[v[k]] = w[k]; //注意理解这行代码
		k = next[k];
	}
	
	flag[1] = 1;
	count++;
	
	//初始化堆
	int h[n+1],size=n; //h数组为堆,size为堆的大小. pos为各点在堆中的位置.
	
	for (int i=0; i<=size; i++) {
		h[i] = i;
		pos[i] = i;
	}
	
	heapAdjust(h, size); //建堆的目的是使第一个为最小的顶点
	deleteTop(h, &size);//删除第一个顶点(加权和里不算自己到自己的距离)

	
	while (count < n) {
		
		int vector = deleteTop(h, &size);
		
		flag[vector] = 1;
		count++;
		sum += dis[vector];
		
		//扫描对应的所有边，进行松弛
		int k = first[vector];
		while (k != -1) {

			if (flag[v[k]]==0 && dis[v[k]] > w[k] ) {
			
				dis[v[k]] = w[k];
				siftup(h, pos[v[k]]);
				
#if DEBUG
				printArray(dis+1, n);
				printArray(h+1, size);
				printArray(pos+1, n);
				printf("----------------------\n");
#endif
			}
			
			k = next[k];
		}

	}
	
	printf("the min weight:%d\n", sum);
	
	return 0;
}


